Order of a matrix = No. of rows × No. of columns

Therefore, Matrix [M] is a matrix of order 3 × 3.

Transpose of a Matrix

if A= [aij] mxn:
    then AT = [bij] nxm where bij = aji

MT  = 1 4 7
     2 5 8
     3 6 9

• (A^T)^T = A
• (A+B)^T = A^T + B^T
• (AB)^T = B^TA^T

1. A+B = B+A (Commutative)
2. (A+B)+C = A+ (B+C) (Associative)
3. AB ≠ BA (Not Commutative)
4. (AB) C = A (BC) (Associative)
5. A (B+C) = AB+AC (Distributive)

Terminologies

• Square Matrix: A square Matrix has as many rows as it has columns. i.e. no of rows = no of columns.
• Symmetric matrix: A square matrix is said to be symmetric if the transpose of original matrix is equal to its original matrix. i.e. (A^T) = A.
• Skew-symmetric: A skew-symmetric (or antisymmetric or antimetric[1]) matrix is a square matrix whose transpose equals its negative.i.e. (A^T) = -A.
• Diagonal Matrix:A diagonal matrix is a matrix in which the entries outside the main diagonal are all zero. The term usually refers to square matrices.
• Identity Matrix:A square matrix in which all the elements of the principal diagonal are ones and all other elements are zeros.Identity matrix is denoted as I.
• Orthogonal Matrix: A matrix is said to be orthogonal if AA^T = A^TA = I.
• Idemponent Matrix: A matrix is said to be idemponent if A² = A.
• Involutary Matrix: A matrix is said to be Involutary if A² = I.
• Singular Matrix: A square matrix is said to be singular matrix if its determinant is zero i.e. |A|=0
• Nonsingular Matrix: A square matrix is said to be non-singular matrix if its determinant is non-zero.

• Syntax for declaring 2-D Array in C++:
  

  data_type  array_name[size1][size2]
  
  Where,
  data_type: Type of data to be stored in the array. 
             Here data_type is valid C/C++ data type
  array_name: Name of the array
  size1: Number of rows
  size2: Number of columns
  
  Example:
  int arr[2][5];
  
  The above example, creates a 2-D array named arr with 
  2 rows and 5 columns in C/C++.
  

• Declaring 2-D array in Java:
  

  data_type[][] array_name = new data_type[size1][size2]
  
  Where,
  data_type: Type of data to be stored in the array. 
             Here data_type is valid Java data type
  array_name: Name of the array
  size1: Number of rows
  size2: Number of columns
  
  Example:
  int arr[2][5];
  
  The above example, creates a 2-D array named arr with 
  2 rows and 5 columns in Java.
  

Accessing 2-D array elements

arr[row_index][column_index]

arr[0][0] = 1;

for i in 1 to m
   for j in 1 to n
      cij = aij + bij

• Addition of matrices is commutative which means A+B = B+A
• Addition of matrices is associative which means A+(B+C) = (A+B)+C
• The order of matrices A, B and A+B is always same
• If order of A and B is different, A+B can’t be computed
• The complexity of addition operation is O(m*n) where m*n is order of matrices

for i in 1 to m
   for j in 1 to n
      cij = aij-bij

• Subtraction of matrices is non-commutative which means A-B ≠ B-A
• Subtraction of matrices is non-associative which means A-(B-C) ≠ (A-B)-C
• The order of matrices A, B and A-B is always same
• If order of A and B is different, A-B can’t be computed
• The complexity of subtraction operation is O(m*n) where m*n is order of matrices

for i in 1 to m
   for j in 1 to p
      cij = 0
      for k in 1 to n
         cij += aik*bkj

• Multiplication of matrices is non-commutative which means A*B ≠ B*A
• Multiplication of matrices is associative which means A*(B*C) = (A*B)*C
• For computing A*B, the number of columns in A must be equal to number of rows in B
• Existence of A*B does not imply existence of B*A
• The complexity of multiplication operation (A*B) is O(m*n*p) where m*n and n*p are order of A and B respectively
• The order of matrix C computed as A*B is O(m*p) where m*n and n*p are order of A and B respectively

first row of destination ------> last column of source
second row of destination ------> second last column of source
.
.
.
.
last row of destination ------> first column of source

Original Matrix: mat[N][N].
Temporary Matrix: temp[N][N].

Copy original matrix into temporary matrix:
for(i = 0; i < N; i++)
{
    for(j = 0; j < N; j++)
    {
        temp[i][j] = mat[i][j];
    }
}

Updating Original Matrix by Rotated Matrix:
// Replace each row in the orginal matrix one by 
// one by columns of the temporary matrix from 
// last to first
for(i = 0; i < N; i++)
{
    for(j = 0; j < N; j++)
    {
        mat[i][j] = temp[j][N-i-1];
    }
}

Without Using Extra Space

First Cycle (Involves Red Elements)
 1  2  3 4 
 5  6  7  8 
 9 10 11 12 
 13 14 15 16 

 
Moving first group of four elements (First
elements of 1st row, last row, 1st column 
and last column) of first cycle in counter
clockwise. 
 4  2  3 16
 5  6  7 8 
 9 10 11 12 
 1 14  15 13 
 
Moving next group of four elements of 
first cycle in counter clockwise 
 4  8  3 16 
 5  6  7  15  
 2  10 11 12 
 1  14  9 13 

Moving final group of four elements of 
first cycle in counter clockwise 
 4  8 12 16 
 3  6  7 15 
 2 10 11 14 
 1  5  9 13 


Second Cycle (Involves Blue Elements)
 4  8 12 16 
 3  6 7  15 
 2  10 11 14 
 1  5  9 13 

Fixing second cycle
 4  8 12 16 
 3  7 11 15 
 2  6 10 14 
 1  5  9 13

vector< data_type > vec_name;

vector< vector < data_type > > vec_name;

• The number of rows in a 2D Vector can be found by calculating the size of the outer vector as vec_name.size().
• The number of items in each row of a 2D Vector can be found by calculating the size of each row as vec_name[i].size().

1 2 3 
4 5 6 
7 8 9 

• Declaration - Syntax:

  data_type[][] array_name = new data_type[x][y];
          For example: int[][] arr = new int[10][20];
  
          

• Initialization - Syntax:

  array_name[row_index][column_index] = value;
          For example: arr[0][0] = 1;
  
          

arr[0][0] = 1

data_type[][] array_name = {
                             {valueR1C1, valueR1C2, ....}, 
                             {valueR2C1, valueR2C2, ....}
                           };

For example: int[][] arr = {{1, 2}, {3, 4}};

arr[0][0] = 1
arr[0][1] = 2
arr[1][0] = 3
arr[1][1] = 4

Accessing Elements of Two-Dimensional Arrays

x[row_index][column_index]

int[][] arr = new int[10][20];

arr[0][0] = 1;

arr[0][0] = 1

1 2 
3 4

Problem #1 : Transpose of a Matrix

void transpose(A[m][n])
{
    B[n][m] // Transpose Matrix

    for ( i=0 to n-1 )
    {
        for ( j=0 to m-1 ) 
            B[i][j] = A[j][i]
    }
}

Problem #2 : Search Element in Row-wise and Column-wise Sorted Matrix

1. The number we are searching for is greater than the current number. This will ensure, that all the elements in the current row is smaller than the number we are searching for as we are already at the right-most element and the row is sorted. Thus, the entire row gets eliminated and we continue our search on the next row. Here elimination means we won’t search on that row again.
2. The number we are searching for is smaller than the current number. This will ensure, that all the elements in the current column is greater than the number we are searching for. Thus, the entire column gets eliminated and we continue our search on the previous column i.e. the column at the immediate left.
3. The number we are searching for is equal to the current number. This will end our search.
Pseudo Code

// matrix size : n*n
void search(mat[][] ,int x)
{
    i = 0, j = n-1
    while(i > n && j >= 0 )
    {
        if (mat[i][j] == x )
        {
            print(i,j)
            break
        }
        else if (mat[i][j] > x )
        {
            j--
        }
        else 
        {
            i++
        }
    }

}

Since, at each step, we are eliminating an entire row or column.
Time Complexity : O(n)
Auxiliary Space : O(1)


---

Problem #3 : Spiral Traversal of Matrix

Description - We are given a 2D Matrix of size m*n. We have to print the Matrix in Spiral form shown in the Example.



Output : 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Solution : We will be traversing the Matrix in Spiral form with the help of 5 variables which includes iterator, starting and ending index of row and columns.

• k - starting row index
• m - ending row index
• l - starting column index
• n - ending column index
• i - iterator
Pseudo Code

void print_spiral(A[][], m, n)
{
    k = 0, l = 0
    while (k < m && l < n)  
    {
        /* Print the first row from the remaining rows */
        for (i=l to n-1)
            print(A[k][i])  
        k++
  
        /* Print the last column from the remaining columns */
        for (i = k to i = m-1 )
            print(A[i][n-1])  
        n-- 
  
        /* Print the last row from the remaining rows */
        if ( k < m) 
        {
            for (i = n-1; i >= l; --i)   
                print(A[m-1][i]) 
            m--
        }
  
        /* Print the first column from the remaining columns */
        if (l < n) :
        {
            for (i = m-1; i >= k; --i)   
                print(A[i][l])   
            l++
        }
    }
}

What is the Determinant of a Matrix?

How to calculate Determinant?

For each element of the first row or first column get cofactor of those elements and then multiply the element with the determinant of the corresponding cofactor, and finally add them with alternate signs. As a base case, the value of the determinant of a 1*1 matrix is the single value itself.

Examples

A = | a   b |
    | c   d |

|A| = (ad - bc)

    | a b c |
A = | d e f |
    | g h i |

|A| = a(ei - fh) - b(di - gf) + c(dh - eg)

Calculating Determinant of an NxN Matrix

• determinantOfMatrix(): This function will accept two parameters, the matrix and its dimension and will return the value of the determinant of the given matrix.
• getCofactor(): This function will return cofactor of the given element in the first row of a given matrix.

• Inside the determinantOfMatrix() function, run a loop from 0 to N for all elements of the first row.
• For every element in the first row, find its cofactor matrix using the getCofactor() function.
• Then, multiply the element with the determinant of the corresponding cofactor, and finally add them with alternate signs.
• To find the determinant of the current co-factor, call the determinantOfMatrix() function recursively, and pass the cofactor matrix and its dimension as parameters.